package 二分;

/**
 * @author: TTDB
 * @create: 2025/9/20
 */
public class searchRange {
    public int[] searchRange(int[] nums, int target) {
        int a = left_bound(nums,target);
        int b = searchright(nums,target);
        //检查边界1 ， 情况留1/2都行
        if(a == -1 || b == -1 ||nums[b] != target) return new int[]{-1,-1};
        return new int[]{a,b};
    }
    // 搜索左侧边界的二分算法
    int left_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        // 注意
        int right = nums.length;

        // 注意
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                //==right
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 注意
                right = mid;
            }
        }
        // 检查出界情况2
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    //right边界
    public int searchright(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left < right){//left = right退出
            int mid = left + (right-left)/2;
            if(nums[mid] < target){
                //左收缩右边界
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        // 这里改为检查 right 越界的情况2
        if (right < 0 || nums[right] != target) {
            return -1;
        }
        return right - 1;
    }
}
